Từ khoảng 1250 trở đi, Islam (Hồi giáo) ngày càng có đông tín đồ trên quần đảo. Đến khoảng 1550 thì trở thành tôn giáo có đông tín đồ nhất trong vùng. Lúc ấy Majapahit đã yếu, và người Bồ Đào Nha bắt đầu đến lập căn cứ. Ít lâu sau đến lượt người Hà Lan. Năm 1619 người Hà Lan đổi tên thành Jayakarta (có nghĩa là Chiến thắng huy hoàng, tức Jakarta, đọc rút ngắn) thành Batavia, tên của chủng tộc tổ tiên họ, và đặt trung tâm hành chính của họ ở đấy. Họ đô hộ phần lớn quần đảo Indonesia đến năm 1945.

Khi người châu Âu đến Đông Nam Á vào giữa thế kỷ 16 thì đã có những nhà nước hùng mạnh ở khắp vùng này. Người Bồ Đào Nha là dân châu Âu đầu tiên có những thuộc địa ở châu Á, Vào thế kỷ 16, họ đã thành lập những thương điếm buôn bán và thuộc địa ở Goa (Ấn Độ), Melaka (Malaysia), Timor (Indonesia), Ma Cao (Trung Hoa), tuy nhiên vào đầu thế kỷ 17, sức mạnh của Bồ Đào Nha đã đối phó với các quốc gia đang nổi lên là Anh và Hà Lan, Công ty Đông Ấn Anh (EIC) và Công ty Đông Ấn Hà Lan (VOC) được thành lập vào các năm 1600 và 1602. Trong gần 200 kế tiếp đó họ là đối thủ thương mại kịch liệt của nhau ở châu Á. Công ty VOC di chuyển để thành lập những trạm buôn bán ở Ấn Độ, Sri Lanka, Đài Loan và Trung Hoa nhằm thu mua sản phẩm của phương Đông, một mục tiêu chính yếu là các đảo có nhiều gia vị, bây giờ là Sulawesi và Maluku ở miền đông Indonesia, thông qua buôn bán với các vương quốc địa phương. Năm 1619, VOC đã tấn công Jayakarta, lúc đó là thành trì và là thành phố buôn bán trọng điểm của vương quốc Banten, phía tây Java, thành phố bị huỷ diệt, người Banten bị đuổi khỏi thành phố, VOC đã thành lập đại bản doanh của mình tại quần đảo này, Jayakarta được người Hà Lan đặt tên lại là Batavia (Jakarta ngày nay).

Công ty VOC đã mở rộng từ từ sự hiện diện của nó tại quần đảo Indonesia. Từ thế kỷ 17-18, nó hành xử như một vương quốc địa phương, liên minh hoặc cắt đứt quan hệ với các vương quốc lân cận, buôn bán rộng rãi cả với Trung Hoa, Ấn Độ và châu Âu.

Tuy vậy, tới năm 1756, VOC mới cai quản được toàn bộ Java, lúc đó nó đã kiểm soát Java, Ambon, và một số khu vực ở miền trung và miền nam Sumatra. Vua Hà Lan đã tiếp quản lại tài sản của VOC, tới thế kỷ 19, chính quyền Đông Ấn Hà Lan đã mở rộng quyền kiểm soát khắp Sumatra và miền đông Indonesia, cùng với sự sụp đổ của hai vương quốc Bali, Acer trước Hà Lan vào các năm 1905, 1911. Lúc đó quá trình thuộc địa đã được hoàn tất khắp Indonesia.

Trong thời kỳ Hà Lan đô hộ, cuộc khởi nghĩa giành độc lập lớn nhất có lẽ là cuộc Chiến tranh Java (1825-1830) giữa hoàng tử Diponegoro và tướng De Kock. Kết quả khoảng 200.000 người chết, trong đó 8.000 là người Hà Lan. Mặc dù người Hà Lan sau này thường nói tới sự hiện diện 3 thế kỷ của họ ở Đông Ấn, song đối với đa số dân cư ở đây, sự sáp nhập vào Đông Ấn chỉ diễn ra vào cuối thế kỷ 19 đầu thế kỷ 20. Niềm tự hào địa phương, văn hóa chính trị và hiểu biết về lịch sử địa phương vẫn mạnh mẽ trong dân chúng cho đến khi người Nhật tiêu diệt đế chế Hà Lan ở đây vào năm 1941